package 我的Java学习_算法基础.day_03;

import static 我的Java学习_算法基础.day_02._015_递归形式进行插入排序.insertSort;

public class _036_绝对中值法 {
    public static void main(String[] args) {
        int[] a ={1,50,34,7,9};
        System.out.println(getMedian(a,0,a.length-1));
    }
    //获取绝对中值数，O(n)的样子
    public static int getMedian(int[] array,int p,int r){
        int size = r - p +1 ;
        //每五个元素一组
        int groupSize = (size%5==0)?(size/5):(size/5+1);
        //存储每组的中间值
        int[] medians = new int[groupSize];
        int indexOfMedian = 0;
        //对每组进行插入排序
        for(int j = 0;j < groupSize;j++){
            //单独处理最后一组，因为最后一组可能不足五个元素
            if(j == groupSize-1){
                insertSort(array,p+j*5,r);
                medians[indexOfMedian++]= array[(p+j*5+r)/2];
            }else{
                insertSort(array,p+j*5,p+j*5+4);
                medians[indexOfMedian++] = array[p+j*5+2];
            }
        }
        insertSort(medians,0,medians.length-1);
        return medians[medians.length/2];
    }
}
